package exercise;

import JZOffer.TreeNode;

public class LCR143 {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) &&
                (cmp(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }

    private boolean cmp(TreeNode A, TreeNode B) {
        if (B == null) {
            // 比较完毕
            return true;
        }

        if (A == null || A.val != B.val) {
            return false;
        }
        return cmp(A.left, B.left) && cmp(A.right, B.right);
    }

    public static void main(String[] args) {
        LCR143 lcr143 = new LCR143();
        TreeNode node1 = new TreeNode(3);
        node1.left = new TreeNode(6);
        node1.right = new TreeNode(7);
        node1.left.left = new TreeNode(1);
        node1.left.right = new TreeNode(8);

        TreeNode node2 = new TreeNode(6);
        node2.left = new TreeNode(1);

        System.out.println(lcr143.isSubStructure(node1, node2));
    }
}
